package com.hsc.sreach;

/**
 * @author
 * @date 2025-05-26
 * @Description 二分查找
 * 给定一个元素 快速查找位置
 */
public class BinarySearch {


    /**
     * 前提是 这个 数组有序
     * 给定一个元素 快速查找返回位置
     * 二分查询的前提是 数组有序
     * 会有一种极端的情况  就是我们要找的值刚好是数组的第一个元素  会执行到最后一步才会找到
     * @param arr
     * @param target
     * @return
     */
    public int binarySearch(int[] arr, int target) {
        // 记录开始的位置
        int  start = 0;
        // 记录结束的位置
        int end = arr.length - 1;
        // 记录中间元素的位置
        int mid = 0;
        // 条件入口判断
        // 如果给定的元素 小于最小值 大于最大值 则返回-1
        // start> end 确保至少会有两个元素
        if (start> end ||target<arr[start] || target>arr[end]){
            return -1;
        }
        // 循环查询元素位置
        // 使用while 循环 当我们不清楚 循环的次数的时候 可以使用 while 但是需要找到临界条件进行退出
        // start和end的范围会一直变化
        while (start<=end){
            // 获取中间元素位置
            mid = (start+end)/2;
            // 目标元素比中间元素 小 在数组的左边
            if (target<arr[mid]){
                //  当目标元素小于 中间元素  则end 缩小范围
                // end： 元素缩小范围 start 元素位置还是从start 开始
                end  = mid-1;
            } else if (target>arr[mid]){
                // 如果目标元素比中间元素 大 在数组的右边
                // start 缩小范围 从middle 开始  end 数组的位置还是end
                start = mid+1;
            }else {
                // 如果以上条件不满足  则与middle 的元素相等
                // 返回middle  数组位置
                return mid;
            }
        }
        // 如果将上面的元素都循环了一遍  还是没有找到  则返回-1
        return -1;
    }

    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(binarySearch.binarySearch(arr, 1));
    }

}
